Digital communication systems are designed to transmit user data in some digitized form from a source to a destination The means coupling the source and destination can be a simple conducting wire, a global satellite system or a data storage system, such as a magnetic disk drive or an optical compact disk. The coupling means is often generalized as a channel between the source and destination.
All channels occasionally introduce noise and distortion into the signals they carry. The noise and the distortion change the transmitted signal and thus can create errors at the output. To protect the information in the transmitted signals as they pass through the channel, error correction systems have been developed that add additional information to the digital signal to be transmitted so that the original signal may be recovered even if the channel introduces errors.
An error correction system consists of an encoder and a decoder, both based on an error correction code (ECC). The encoder, used at the information source, computes a certain amount of parity check symbols from the user data to be transmitted or stored. The encoding is done by applying an encoding rule to the user data. Then, the user data and the parity check symbols, together known as codewords, are all transmitted or stored through the channel and may be corrupted by noises and distortions. At the destination, a detector is used to estimate the codewords transmitted or stored through the channel. The decoder at the destination takes in the estimations of the codewords and attempts to recover the original user data according to the encoding rule.
Because of the noises and distortions in the channel, the detector occasionally makes incorrect estimations. Consequently, the input to the decoder has errors. Sometimes the detector is not able to make a clear estimation from its input. In this case, the detector can flag some positions as erasures in the estimated codeword.
The error correction capability of a particular ECC is determined by its minimum Hamming distance, usually denoted as d. For such a code, there exist decoding algorithms that can correct t errors and recover s erasures as long as d>2t+s. In order to correct errors, the decoder tries to figure out whether there is any errors in the estimation and if there is, determine the position and the value of the errors and correct them. To recover erasures, the decoder makes decisions on erasures at known positions based on the code structure. Sometimes the decoder can not find a valid codeword, subject to the encoding rule, because of excessive errors or erasures in its input. In this case, the decoder may declare a failure in decoding.
In many digital communication systems, the data is processed in blocks independent of each other rather than individual symbols. For example, in some communication networks, data is transmitted and received in packets. In data storage devices, data is stored or retrieved in sectors. For the same amount of redundancy, maximum ECC protection of such blocks of data can be achieved by encoding every block of data into one single codeword. However, the encoder and decoder for such codes are usually too complicated to implement because the code required is too long. Thus, several shorter codewords are used to encode the whole block. In channels where burst error is a significant source of error, interleaving is used to spread a single long burst error to multiple codewords so that the error correction capability of several codewords can be combined to combat burst errors.
An example of an interleaving error correction system is found in the system used in storing and retrieving data from some magnetic storage devices. It is very important for the error correction system in these devices to be able to recover data suffering from long burst errors, which may result from defects in the storage media.
In a typical situation, user data is stored and retrieved in sectors. Each sector has 512 bytes of user data. The ECC of choice is a Reed-Solomon code over finite field 28, whose symbol happens to be an 8-bit byte. The maximum length of a codeword of this code is 255 bytes, including the parity check symbols. Therefore, at least three codewords are needed to protect one sector. If three codewords are used, there are 171 bytes of user symbols in each codeword. By appending 4 parity check bytes to each 171-byte group, a code with minimum Hamming distance of 5 can be constructed. Then, storing, one after the other, a corresponding byte from each codeword and doing so repeatedly until all the bytes have been transmitted. Thus, the complete set of user bytes and ECC bytes for any one codeword can be found by sampling every third byte of the interleaved block. This is often referred to as a three-way bytewise interleave. The series of interleaved codewords is transmitted through the channel where it is occasionally corrupted by burst errors. The burst errors usually affect two or more consecutive bits and, because of the interleaving, corrupt two or more codewords.
Interleaving reduces the effects of burst errors on the ECC encoded signal. Burst errors are short duration error events affecting one or more consecutive symbols. By ensuring that consecutive words in the ECC encoded signal are not from the same codeword, interleaving reduces the chance that a burst error will affect more than one symbol in a codeword. If ECC can typically only correct two user bytes per codeword, interleaving will reduce the chances that a burst error will exceed the maximum number of symbols that can be corrected.
After being retrieved from the channel, the detector decodes the interleaved transmitted sequences into estimations of the ECC encoded signal. If a single block suffers from one very long burst error or more than one burst, the ECC decoder may not be able to correct the corrupted data because more than the maximum number of symbols of ECC encoded data will be corrupted in a single ECC codeword. In general, the single burst error correction capability is limited to L×t0 symbols, where L is the number of codewords in the interleaved block and to is the random error correction capability of an individual codeword. The random error correction capability of an individual codeword can be determined by the particular ECC employed and the number of parity check blocks added to that codeword. It is well known in the art that decoders exist for typical ECCs that can be used to simultaneously correct errors at unknown positions and recovery erasures at known positions.
In some prior art systems, the number of parity check symbols to be added to each codeword is the same. When the interleaved block is decoded, if the decoder fails to decode any one of the codewords, the attempt to decode the whole block is considered a failure.
In other prior art systems, there is a first number of parity check blocks added to a selected codeword and there is a second number of parity check blocks that are added to the remaining codewords. In the latter prior art, a dual decoder system is implemented having two decoders with differing error correction codes, wherein each of the codes has a different error correction capability. The first decoder has a greater single burst error correction capability than the second decoder. During the encoding routine, parity check symbols are added to each codeword, but one codeword is selected from the number of codewords and more parity check symbol are added to the selected codeword. Thus, the selected codeword has a greater error correction capability than the other codewords. In relation, the first decoder allows correction of the errors in the selected codeword. When decoding the selected codeword and a correctable error is detected, the dual-decoder system assumes that errors exist in adjacent positions of the other codewords.
The adjacent positions to the correctable error positions of the first decoded codeword are identified as erasures in the other codewords and then used in the decoding of the subsequent codewords. This allows an increment in the burst error correction capability of the whole block. There are some major weaknesses of this prior art. First, hardware ECC decoders are very sophisticated circuits, so dual decoders at the destination incurs extra complexity in hardware and development, especially for high data rate applications. Thus, the requirement of using two different decoders to decode an interleaved codeword is not desirable. A very important fact is that, in many systems, the encoding method, or equivalently, the signal format transmitted through the channel or the data format stored in the media, is already fixed because of the necessity of supporting existing legacy systems or open standards. Most of these systems use only one code and interleave. This prior art cannot be applied because it requires a change in the encoding scheme.
Therefore, there is a need in the technology to provide a more efficient method to encode and decode a data signal in a communication system that can be used with existing systems and standards.
The present invention provides a solution to this and other problems, and offers other advantages over the prior art.